#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int len = maxHeights.size();
        vector<long long> f(len + 10, 0);
        vector<long long> p(len + 10, 0);
        stack<int> st;

        for (int i = len - 1; i >= 0; i--) {
            while (!st.empty() && maxHeights[st.top()] > maxHeights[i])st.pop();
            if (st.empty()) {
                int num = len;
                f[i] = (long long)maxHeights[i] * (num - i) + f[num];
            }
            else {
                int num = st.top();
                f[i] = (long long)(num - i) * maxHeights[i] + f[num];
            }
            st.push(i);
        }
        while (!st.empty()) {
            //cout<<st.top()<<" ";
            st.pop();
        }
        // cout<<endl;
        // for(int i=0;i<len;i++){
        //     cout<<f[i]<<" ";
        // }
        for (int i = 0; i < len; i++) {
            while (!st.empty() && maxHeights[st.top()] > maxHeights[i])st.pop();
            if (st.empty()) {
                int num = -1;
                p[i] = (long long)maxHeights[i] * (i + 1);
            }
            else {
                int num = st.top();
                p[i] = (long long)(i - num) * maxHeights[i] + p[num];

            }
            st.push(i);
        }

        //cout<<endl;
        //   while(!st.empty()){
        //     cout<<st.top()<<" ";
        //     st.pop();
        // }
        // for(int i=0;i<len;i++){
        //     cout<<p[i]<<" ";
        // }
        long long ans = 0;
        for (int i = 0; i < len; i++) {
            ans = max(ans, p[i] + f[i] - maxHeights[i]);
        }
        return ans;

    }
};